#include "lib/binary_tree.h"
#include "main/utils.h"
using namespace std;

using TreeNode = BinaryTreeNode;

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
      dfs(root);
      return {repeat.begin(), repeat.end()};
    }
    string dfs(TreeNode* node) {
      if (!node) {
        return "";
      }
      string str = to_string(node->value) + "(" + dfs(node->left) + ")(" + dfs(node->right) + ")";
      auto it = seen.find(str);
      if (it == seen.end()) {
        seen[str] = node;
      } else {
        repeat.insert(it->second);
      }
      return str;
    }
private:
    unordered_map<string, TreeNode*> seen;
    unordered_set<TreeNode*> repeat;
};

int main() {
  auto node1 = CreateBinaryTreeNode(1);
  auto node2 = CreateBinaryTreeNode(2);
  auto node3 = CreateBinaryTreeNode(3);
  auto node4 = CreateBinaryTreeNode(4);
  auto node5 = CreateBinaryTreeNode(2);
  auto node6 = CreateBinaryTreeNode(4);
  auto node7 = CreateBinaryTreeNode(4);

  ConnectNode(node1, node2, node3);
  ConnectNode(node2, node4, nullptr);
  ConnectNode(node3, node5, node6);
  ConnectNode(node5, node7, nullptr);

  Solution su;
  auto ret = su.findDuplicateSubtrees(node1);
  for (int i = 0; i < ret.size(); ++i) {
    PrintBinaryTree(ret[i]);
  }
  DeleteBinaryTree(node1);

  return 0;
}
